A problem of considerable practical importance in circuit design is that of finding the DC operating point of a nonlinear circuit. The operating point, apart from being important in itself, is a prerequisite for subsequent tasks such as small-signal, transient, and noise analyses that are repeatedly invoked in the design of a circuit. From a simulation standpoint, finding an operating point corresponds to solving a system of nonlinear equations describing the circuit. The Newton-Raphson method, widely used in circuit simulators for solving nonlinear equations, often fails to converge to a solution. Despite the advent of other approaches (e.g., stepping or pseudo-transient), no technique has emerged that solves the operating point problem reliably and efficiently. As a result, DC convergence problems often create a significant bottleneck in the design process, especially for large circuits.
Homotopy or continuation methods are a relatively recent numerical technique for solving systems of nonlinear equations. These methods are appealing because they can be proven to be globally convergent, a property that eludes other nonlinear solution techniques. Previous applications of homotopy to solving the operating point problem include parameter switching, piecewise-linear ("PL") methods and arclength continuation. Despite the guarantee of convergence offered by the theory of homotopy, however, problems related to efficiency and numerics encountered in it has not so far had a significant impact on practical circuit simulation and design. So far, the successful use of homotopy on circuits containing more than a few nonlinear devices, or using realistic nonlinear device models, has so far been limited to medium-sized bipolar circuits.
The principle of continuation is similar to that of source or gmin stepping. (Stepping is also known as "monotonic continuation," familiar to users of circuit simulators, such as SPICE.) The circuit equations are modified by introducing a single continuation parameter .lambda.. The parameter .lambda. is first set to a value (.lambda.=0 by convention) at which the circuit becomes easy to solve or its solution becomes known. The parameter .lambda. is then slowly changed back to a value at which the original circuit is retrieved (.lambda.=1) and simultaneously, the solution of the changing circuit is followed. The underlying hypothesis is that small changes in the parameter .lambda. cause small changes to the circuit and its solution, hence the new solution is relatively easy to obtain using numerical techniques with local convergence properties (e.g., the Newton-Raphson method). It appears natural to expect this hypothesis to hold for circuits described by equations that are smooth (i.e., continuous and several times differentiable).
For many practical circuits, however, this assumption is not true. One example is the Schmitt trigger circuit, where stepping can fail at critical values of the continuation parameter because the state of the circuit can change abruptly from low to high (and vice versa) for even the slightest monotonic change in the parameter. The phenomenon is illustrated in FIG. 1. As supply voltage V.sub.cc is stepped upward from 0 V, the output characteristic 100 of the circuit (not shown) suffers a large jump 110 at V.sub.cc .apprxeq.4.5 V. Points where monotonic increases or decreases of the continuation parameter lead to an abrupt jump in the solution are termed "turning points" or "folds." Many practical feedback systems composed of smoothly-behaved components exhibit turning points that can cause stepping algorithms to fail.
It is in the treatment of turning points that homotopy differs from stepping. By appropriately incrementing or decrementing the continuation parameter, discontinuities in the solution are avoided when turning points are encountered. For the Schmitt trigger output characteristic 100 of FIG. 1, this corresponds to reducing V.sub.cc after th turning point at V.sub.cc .apprxeq.4.5 V is reached, taking care to follow the central section of the output characteristic 100 and not backtrack onto the initial section already covered. Another turning point 120 is reached at V.sub.cc .apprxeq.3 V, after which V.sub.cc is increased again and the lower right section of the output characteristic 100 followed.
Some versions of continuation (e.g., parameter switching) rely on the detection and special treatment of turning points. Arclength continuation, on the other hand, can negotiate turning points automatically without their explicit detection. Its power stems from that it does not treat the continuation parameter .lambda. differently from the unknowns of the circuit being solved for, but treats it s another unknown whose next value on the curve it determines. For the Schmitt trigger circuit of FIG. 1, the process corresponds to "walking" along the output characteristic 100 without paying special heed to curvature and folds or treating V.sub.cc as special. More precisely, the technique solves a special ordinary differential equation (the "defining ODE") that produces as output a sequence of values of .lambda. (in general not monotonically increasing) together with solutions of the circuit at these values of .lambda.. The key property of this sequence is that a point where .lambda.=1 is always reached; therefore that point is the desired solution of the original circuit.
Any nonlinear circuit's equations can be put in the general form (barred variables denote vectors): EQU g(x)=0 (1)
To apply homotopy, the parameter .lambda. is embedded into this system to yield a related system: EQU f(x,.lambda.)=0 (2)
The embedding of .lambda. is designed so as to reduce f to the original system at .lambda.=1, i.e., f(x,1).apprxeq.g(x). In addition, a start system f(x,0)=0 is constructed so as be easy to solve by traditional methods. By solving the defining ODE for the problem, the arclength continuation algorithm generates samples {(x.sup.i,.lambda..sup.i)} of the continuation track. Every point on the track satisfies Equation 2, hence, when .lambda..sup.i =1 is reached, x.sup.i is a solution of g(x)=0.
Different types of homotopy continuation tracks are possible, as illustrated in a graph in FIG. 2. The horizontal axis of the graph in FIG. 2 depicts the progress of a single .lambda., which varies between 0 and 1. The vertical axis of the graph in FIG. 2 represents the solution of the circuit at a given value of the single .lambda.. The homotopy algorithm starts at .lambda.=0 and generates points on the track until .lambda.=1 is reached.
It can be shown that the top four kinds of track 210, 220, 230, 240 in FIG. 2 cannot occur with arclength continuation, and that the situation depicted by the fifth (dashed bold) track 250 is extremely unlikely to occur (a probability-0 event). Another possibility (not illustrated), a bounded space-filling curve that does not reach .lambda.=1, can also be shown to be impossible. A lowermost track 260 illustrates the normal, extremely likely (or probability-1) case of tracks that reach .lambda.=1 without bifurcations.
An important concept in arclength continuation is that of the tangent vector, which has a simple interpretation: it is the tangent to the track at any point. Two instances 261, 262 of the tangent vector are shown on the lowermost track. Generally speaking, the algorithm proceeds by calculating the tangent vector from which it determines the next point on the curve by extrapolation. Turning points correspond to the .lambda.-component of the tangent vector becoming 0; two turning points are shown on the lowermost curve in FIG. 2.
How .lambda. is embedded in f is crucial for continuation to work robustly and efficiently in practice. A simple embedding that satisfies the requirements of arclength continuation is the following: EQU f(x,.lambda.).apprxeq..lambda.g(x)+(1-.lambda.)(x-a) (3)
where a is a constant vector. The above equation has a simple circuit interpretation: the current through each device is multiplied by .lambda. and new resistors and current sources are added from each node to ground, of conductance 1-.lambda. and current (1-.lambda.)a.sub.i respectively. A variation is to consider only the nonlinear elements (e.g., metal oxide semiconductor, or "MOS", devices) when adding the conductances.
Turning now to FIG. 3, illustrated is a simple, prior art homotopy 300 for MOS devices. Currents through a resistor 310 are multiplied by 1-.lambda. while the currents through a MOS 320 are multiplied by .lambda., as indicated by Equation (3). This straightforward embedding of the prior art is, however, ineffective for most large circuits. Excessively long tracks or outright failure of the numerical method for solving the defining ODE result. Solving for an operating point using arclength continuation with this embedding can be inferior to even traditional Newton-Raphson methods.
Therefore, what is needed in the art is a technique to allow successful practical application of arclength continuation to the operating point problem for large circuits, typically primarily comprising transistor or MOS devices to allow such circuits to be efficiently designed and manufactured.